package fun.coding.geeksforgeeks;

import java.util.LinkedList;
import java.util.List;

import fun.coding.leetcode.LeetCodeHelpers;

public class PrintAllPathsOfMatrix {
	// Print all possible paths from top left to bottom right of a m x n matrix
	// http://www.geeksforgeeks.org/print-all-possible-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/
	public static void main(String[] args) {
		PrintAllPathsOfMatrix ins = new PrintAllPathsOfMatrix();
		
		int[][] test1 = {{1, 2, 3}, {4, 5, 6}};
		List<List<Integer>> res1 = ins.printAllPaths(test1);
		LeetCodeHelpers.printListOfList(res1);
	}
	
	// It is a very typical DFS, with variables keeping and removing
	// Think about finishing on the right, remove all the elements, then finish all the down part
	public List<List<Integer>> printAllPaths(int[][] matrix) {
		List<List<Integer>> res = new LinkedList<List<Integer>>();
		if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;
		
		
		List<Integer> cur = new LinkedList<Integer>();
		helper(matrix, 0, 0, res, cur);
		return res;
	}
	
	private void helper(int[][] matrix, int i, int j, List<List<Integer>> res, List<Integer> cur) {
		int row = matrix.length;
		int col = matrix[0].length;
		
		cur.add(matrix[i][j]);
		
		if (i == row - 1 && j == col - 1) {
			res.add(new LinkedList<Integer>(cur));
			return ;
		}
		
		if (j + 1 < col) {
			helper(matrix, i, j+1, res, cur);
			cur.remove(cur.size() - 1);
		}
		
		if (i + 1 < row) {
			helper(matrix, i+1, j, res, cur);
			cur.remove(cur.size() - 1);
		}
	}

}
